package com.demo.algorithms.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * 插入排序：复杂度为O(n2)（插入即表示将一个新的数据插入到一个有序数组中，并继续保持有序）
 * 插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，
 * 从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，
 * 外层循环对除了第一个元素之外的所有元素，
 * 内层循环对当前元素前面有序表进行待插入位置查找，并进行移动；
 * <p>
 * 缺点；当需要插入的数据较小时，后移的次数明显增多，影响性能。
 * 因此产生了希尔排序。
 *
 * @author: 蔡奇峰
 * @date: 2020/7/18 22:23
 **/
public class InsertionSorting {

    public static void main(String[] args) {
//        int[] arr = {6, 2, 5, 2, 8, 66, 22, 17, 18, 1, 88, 98, 168, 178};
        int[] arr = new int[7780];
        for (int i = 0; i < 7780; i++) {

            arr[i] = new Random().nextInt(1800);
        }
        System.out.println("数组排序前：" + Arrays.toString(arr));

        long timeMillis = System.currentTimeMillis();
        insertSort(arr);
        long timeMilli = System.currentTimeMillis();

        System.out.println("数组排序后：" + Arrays.toString(arr));

        System.out.println("插入排序耗时：" + (timeMilli - timeMillis));
    }

    /**
     * 插入排序：从数组中逐个元素作为插入元素，和前面的进行比较，小的即插入前面。
     * 前面的已经是排序了。
     *
     * @param arr 需要排序的数组
     */
    public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            // 插入的下标，默认是前一位
            int insertIndex = i - 1;
            // 插入的值
            int insertValue = arr[i];
            // 插入的值和前面的进行比较，小则插入。排序：从小到大，改大于号则排序为从大到小
            while (insertIndex >= 0 && insertValue < arr[insertIndex]){
                // 交换，将小的放前面，保证前面是已经排序后的
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex --;
            }

            if(insertIndex != i - 1) {
                arr[insertIndex + 1] = insertValue;
            }
//            System.out.println("第" + i + "轮：" + Arrays.toString(arr));
        }

    }

}
